package bloomfilterdemo;

import java.util.BitSet;

class SimpleHash {

    public int cap;//当前容量
    public int seed;//随机

    public SimpleHash(int cap,int seed) {
        this.cap = cap;
        this.seed = seed;
    }
    public SimpleHash(){

    }

    //根据seed不同 创建不能的哈希函数
    int hash(String key) {
        int h;
        //(n - 1) & hash
        return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }

}
public class MyBloomFilter {

    public static final int DEFAULT_SIZE = 1 << 20;
    //位图
    public BitSet bitSet;
    //记录存了多少个数据
    public int usedSize;

    public static final int[] seeds = {5,7,11,13,27,33};

    public SimpleHash[] simpleHashes;

    public MyBloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[seeds.length];
        for (int i = 0; i < simpleHashes.length; i++) {
       simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);

        }
    }

    /**
     * 添加元素 到布隆过滤器
     * @param val
     */
    public void add(String val) {
        //让X个哈希函数  分别处理当前的数据
        for (SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            //把他们 都存储在位图当中即可
            bitSet.set(index);
        }
    }
    /**
     * 是否包含val ，这里会存在一定的误判的
     * @param val
     * @return
     */
    public boolean contains(String val) {
        //val  一定 也是通过这个几个哈希函数去 看对应的位置
        for (SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            //只要有1个为 0     那么一定不存在
            boolean flg = bitSet.get(index);
            if(!flg) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("hello");
        myBloomFilter.add("hello2");
        myBloomFilter.add("bit");
        myBloomFilter.add("haha");

        System.out.println(myBloomFilter.contains("hello"));
        System.out.println(myBloomFilter.contains("hello3"));
        System.out.println(myBloomFilter.contains("he"));
    }
}